package tree_1030;


import oj.oj_144.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

import java.util.*;

public class TreeOperations {
    public static void levelorder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 使用队列而不是栈，没有递归
        // 因为队列中取出元素后需要把结点的左右孩子继续放进去，所以这里队列的元素类型是 TreeNode
        Queue<TreeNode> queue = new LinkedList<>();
        // 首先把根节点放入队列中，此时此刻的层序遍历不会把 null 放到队列中
        // 所以，所以需要考虑 root == null 的情况
        queue.offer(root);

        // 开启循环，直到 queue.isEmpty() == true
        while (queue.isEmpty() == false) {
            // 1. 取出队首元素
            TreeNode node = queue.poll();
            // 断言 node != null
            // 2. 打印结点的值
            System.out.println(node.toString());
            // 3. 依次从左到右把孩子放入队列中，不放 null 进去
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    public static TreeNode 手动构建二叉树() {
        TreeNode a = new TreeNode('A'); // 'A' 是 char 类型，char -> int 类型，就是这个字符的 unicode 编码（ascii 是 unicode 编码的子集）
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        // 手动构建其关系
        a.left = b; a.right = c;
        b.left = d; b.right = e;
        c.left = f; c.right = g;
        d.left = null; d.right = null;  // 这行可以省略
        e.left = null; e.right = h;
        f.left = null; f.right = null;
        g.left = null; g.right = null;
        h.left = null; h.right = null;

        // 返回根结点即可
        return a;
    }

    public static int sizeOf(TreeNode root) {
        if (root == null) {
            // 空树的结点个数
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int size = 0;
        // 每个结点都会被放入队列中
        // 都会被取出来一次
        // 有多少个结点，这个循环就会持续多少次
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            size++; // 打印替换成 size++
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        return size;
    }

    public static int leafSizeOf(TreeNode root) {
        if (root == null) {
            // 空树的叶子结点个数
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int size = 0;
        // 每个结点都会被放入队列中
        // 都会被取出来一次
        // 有多少个结点，这个循环就会持续多少次
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 只有叶子结点时，才 size++
            if (node.left == null && node.right == null) {
                size++; // 打印替换成 size++
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        return size;
    }

    // 代码实现层面，需要把 结点和层数打包在一起，作为队列的元素
    // 代码中如何体现打包呢？使用一个对象
    static class TreeNodeWithLevel {
        public TreeNode node;
        public int level;

        public TreeNodeWithLevel(TreeNode node, int level) {
            this.node = node;
            this.level = level;
        }

        @Override
        public String toString() {
            return String.format("%s-%d", node.toString(), level);
        }
    }
    public static void levelOrderButLevel(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root, 1));

        while (!queue.isEmpty()) {
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;
            System.out.println(tnwl);

            if (node.left != null) {
                queue.offer(new TreeNodeWithLevel(node.left, level + 1));
            }

            if (node.right != null) {
                queue.offer(new TreeNodeWithLevel(node.right, level + 1));
            }
        }
    }

    public static void levelOrderButLevel2(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> levelQueue = new LinkedList<>();

        nodeQueue.offer(root);
        levelQueue.offer(1);

        // 代码一定维护着 nodeQueue 和 levelQueue 的元素个数一定是一样的
        // 所以判断，只需要判断其中一个队列是 empty 即可
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int level = levelQueue.poll();

            System.out.println(node + "-" + level);

            if (node.left != null) {
                nodeQueue.offer(node.left);
                levelQueue.offer(level + 1);
            }

            if (node.right != null) {
                nodeQueue.offer(node.right);
                levelQueue.offer(level + 1);
            }
        }
    }

    public static int getKLevelSize(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root, 1));

        int size = 0;
        while (!queue.isEmpty()) {
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;
            if (level == k) {
                // 说明是第 k 层了
                size++;
            }

            if (node.left != null) {
                queue.offer(new TreeNodeWithLevel(node.left, level + 1));
            }

            if (node.right != null) {
                queue.offer(new TreeNodeWithLevel(node.right, level + 1));
            }
        }

        return size;
    }

    public static int heightOf(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root, 1));

        int height = -1;
        while (!queue.isEmpty()) {
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;

            height = level; //后边的值覆盖前面的值

            if (node.left != null) {
                queue.offer(new TreeNodeWithLevel(node.left, level + 1));
            }

            if (node.right != null) {
                queue.offer(new TreeNodeWithLevel(node.right, level + 1));
            }
        }

        // height 就是最后一个 level，也就是最大的 level
        return height;
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        // 定义两个队列
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> levelQueue = new LinkedList<>();

        // 根结点记为第 0 层
        // 把根结点和它对应的层数放入队列中
        nodeQueue.offer(root);
        levelQueue.offer(0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int level = levelQueue.poll();

            // 每个结点的 level 就刚好对应 ans 中的下标，根据这个下标，就可以获取到对应的 List<Integer>，这层的 List
            List<Integer> levelList = ans.get(level);
            // 将元素放入对应的 levelList 中（尾插，保证顺序不变）
            levelList.add(node.val);

            // 层序遍历的模板代码
            if (node.left != null) {
                nodeQueue.offer(node.left);
                levelQueue.offer(level + 1);
            }

            if (node.right != null) {
                nodeQueue.offer(node.right);
                levelQueue.offer(level + 1);
            }
        }

        return ans;
    }

    // 判断是否是完全二叉树
    public static boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            // 空树是一种完全二叉树
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 循环停止的条件，从队列中取出的元素是 null
        while (true) {
            TreeNode node = queue.poll();
            if (node == null) {
                break;
            }

            queue.offer(node.left);
            queue.offer(node.right);
        }

        // 检查队列中剩余的元素是否存在 != null 的情况
        // 存在 != null：非完全二叉树
        // 任取 == null：完全二叉树
        // 所以，遍历队列中剩余的元素
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                // 存在 != null：
                return false;
            }
        }

        // 任取 == null：是完全二叉树
        return true;
    }

    public static void preorder非递归(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 使用 Deque 作为栈来使用
        TreeNode cur = root;

        // 循环停止的条件 cur == null && stack.isEmpty()
        // cur == null 的时候，应该处理 栈 中还有结点的右子树了
        // 但 栈 也是 empty，说明所有的右子树都处理
        // 所以可以停止了
        // 反过来，循环继续的条件
        // !(cur == null && stack.isEmpty())
        // 化简 cur != null || stack.isEmpty() == false
        while (cur != null || stack.isEmpty() == false) {
            // 一路朝左走，不管右子树，但需要回溯，所以记录在栈中
            while (cur != null) {
                System.out.println(cur.toString());
                stack.push(cur);
                cur = cur.left;
            }

            // 依次从栈中弹出元素，处理剩下没走的右子树
            TreeNode top = stack.pop();

            // 处理右子树
            cur = top.right;
        }
    }

    // 中序遍历是第二次经过时打印（从左子树回来时打印） -> 从栈里弹出来的时候打印
    public static void inorder非递归(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 使用 Deque 作为栈来使用
        TreeNode cur = root;

        while (cur != null || stack.isEmpty() == false) {
            while (cur != null) {
                // 第一次经过某结点
                stack.push(cur);
                cur = cur.left;
            }

            // 依次从栈中弹出元素，处理剩下没走的右子树
            TreeNode top = stack.pop();
            System.out.println(top);    // 第二次经过某结点

            // 处理右子树
            cur = top.right;
        }
    }

    // 因为之前的代码，第二次经过结点时，就把结点从栈里 pop 了，所以，没有第三次经过结点的机会了
    // 想办法弄出第三次经过 —— 后序遍历
    public static void postorder非递归(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 使用 Deque 作为栈来使用
        TreeNode cur = root;
        TreeNode last = null;   // 记录上次后序遍历经过的结点

        while (cur != null || stack.isEmpty() == false) {
            while (cur != null) {
                // 第一次经过某结点
                stack.push(cur);
                cur = cur.left;
            }

            // 查看栈顶元素
            TreeNode top = stack.peek();
            if (top.right == null) {
                // 右子树为空的情况下，没必要走第三次
                // 换言之：第二次可以看作第三次
                System.out.println(top);    // 后序
                last = top; // last 记录上一次被后序遍历的结点

                stack.pop();
            } else if (top.right == last) {
                // 上一次后序遍历的结点是 top 的右孩子
                // 说明是从 top 的右边来到 top 的
                // 也就是第三次经过 top 结点
                System.out.println(top);    // 后序
                last = top; // last 记录上一次被后序遍历的结点

                stack.pop();
            } else {
                // 说明是从 top 的左边到的 top
                // 第二次经过 top 结点
                // 不后序遍历，而是继续走 top 的右子树
                // 处理右子树
                cur = top.right;
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = 手动构建二叉树();
        postorder非递归(root);

//        System.out.println(isCompleteTree(root));

//        List<List<Integer>> lists = levelOrder(root);
//        System.out.println(lists);

//        levelOrderButLevel2(root);
//        System.out.println(heightOf(root));
//        System.out.println(getKLevelSize(root, 1));
//        System.out.println(getKLevelSize(root, 2));
//        System.out.println(getKLevelSize(root, 3));
//        System.out.println(getKLevelSize(root, 4));
//        System.out.println(getKLevelSize(root, 5));
//        System.out.println(getKLevelSize(root, 6));
//        levelOrderButLevel(root);

//        System.out.println(sizeOf(root));
//        System.out.println(leafSizeOf(root));

//        levelorder(root);
    }
}